package com.structure.demo;

import org.apache.commons.lang3.StringUtils;

/**
 * 冒泡排序
 * Created by shuttle on 18/10/10.
 */
public class BubbleSort {
    /**
     * 需要被排序的数组
     */
    private static int[] arrayToBeSort = {31, 45, 32, 14, 12, 5, 3, 2, 8};

    /**
     * 冒泡排序是从最右端开始取元素向左挨个比较，将较小的同左边进行交换
     * 多次循环后，完成整体的排序
     *
     * @param args
     */
    public static void main(String[] args) {
//        /**
//         * 设置一个比较的起点，默认为素组的起始位置，当有较小的元素被移动到左端后，不需要再进行比较时，该值+1
//         */
//        int k = 0;
//        /**
//         * 只需要比较数组长度-1次
//         */
//        while (k < arrayToBeSort.length - 1) {
//            k = statCompare(k);
//        }
//
//        System.out.println("排序结束！");
        BubbleSort.BubbleSort(arrayToBeSort);
    }

    /**
     * 递归比较
     *
     * @param endPosition 结束比较的位置
     */
    private static int statCompare(int endPosition) {
        /**
         * 最右边的值已经取出来了，所以取倒数第二个值比较，这里记录位置
         */
        int startPosition = arrayToBeSort.length - 2;

        /**
         * 临时变量记录需要被比较的值, 首先赋值素组最右侧的值
         */
        int temp = arrayToBeSort[arrayToBeSort.length - 1];

        for (int i = startPosition; i >= endPosition; i--) {
            if (temp < arrayToBeSort[i]) {
                //因为temp的值始终比当前比较的值位置靠右以为，所以直接交换
                arrayToBeSort[i + 1] = arrayToBeSort[i];
                arrayToBeSort[i] = temp;
            } else {
                temp = arrayToBeSort[i];//否则更新temp的值为最小的值
            }
        }
        String result = "";
        for (int i = 0; i < arrayToBeSort.length; i++) {
            result += arrayToBeSort[i] + ",";
        }
        System.out.println("第" + (endPosition + 1) + "次排序结果:" + result);
        return endPosition + 1;
    }
    static int total = 0;

    /**
     * 直接循环比较
     * @param arr
     */
    public static void BubbleSort(int[] arr) {
        int temp;//定义一个临时变量
        for (int i = 0; i < arr.length - 1; i++) {//冒泡趟数
            for (int j = arr.length - 1; j > i; j--) {
                total++;
                if(arr[j] < arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
            String str = "";
            for (int m = 0; m < arr.length; m++) {
                str += arr[m] + ",";
            }
            System.out.println("第" + i + "次排序:" + str);
        }

        System.out.println("总循环次数：" + total);
    }
}
